All integrated circuits and their physical packaging are described by physical designs in the form of hierarchical 2-dimensional geometric models. The complexity of these designs quadruples approximately every 3 years. For example, a typical 16Mega-bit memory physical design in 1989 was described by 150,000,000 geometric mask shapes on 71 design levels. A typical 64 Mega-bit memory physical design in 1992 is described by 600,000,000 geometric mask shapes on 127 levels. This increasing data volume is becoming a significant problem for engineering design automation, since it overstresses the software design tools which in turn impact the design cycle time, design cost and time to market.
Physical design data is analysed many times to verify that physical mask constraints are not exceeded, electrical performance is satisfactory, and the physical design implements the logical design intent. Such analysis is extremely detailed. For example, the checking of physical constraints requires that hundreds of specific physical ground rules are checked. Given the enormous number of geometric mask shapes, such analysis consumes thousands of mainframe CPU hours. Physical design verification is an important phase in the design cycle of an integrated circuit and is key to delivering first-pass working designs to a chip producer for fabrication. The high cost of integrated circuit fabrication plus the need to keep the design cycle time short for competitive reasons dictates the need for an efficient verification system that can be exercised many times throughout the physical design phase. It is therefore of importance to be able to analyse increasingly complex designs in a time efficient manner.
In the prior art, the standard approach to managing increasing design complexity has been to optimize the hierarchical design itself, but verify, or check the design in flattened form. According to this methodology, the design is sub-divided into arbitrary design partitions that can be analysed individually. However, each partition is ultimately analyzed as one monolithic circuit, that is as a flat design. This approach relies on the ability of the designer to generate a high level view of each design partition, which view can be used at the next higher level of the hierarchy to characterise the design partition without exposing its detailed internal data. For example, such hierarchical characterisation is typically used to define the wiring channels and connection ports that can be used to route wire over a design partition in the higher level cell.
The prior art design verification methodology suffers from several problems. The computation of the high level representation of the physical partitions can be a significant problem when the data volume in a partition is substantial. Unfortunately, the addition of these high level representation cells to the design increases the complexity still further. Moreover, any attempt to break the hierarchical design constraints using ad-hoc design fixes invalidates the integrity of the hierarchical partitioning and reduces the verification process to a completely flat analysis problem. Finally, the methodology constraints typically prevent the designer from fully exploiting the available density offered by the physical design technology.
Hierarchical design optimization helps to manage the problem of design complexity, but does nothing to correct the deficiencies in the shape manipulation algorithms of verification tools when these tools are subjected to increasing data volume. The primary reason for this is that mask data is ultimately analysed flat, i.e., all instances of mask shapes are transformed into the coordinate system of the root node of the design, whereas mask data is typically designed nested, i.e., the mask shapes are designed hierarchically and may be reused in the design many times. It is the flattening process that expands the data volume considerably and leads to over-stressing the tools.
Recent advances have been made in dealing with the problem of expanding data volume. These advances capitalize on the highly nested nature of hierarchical design data using a graphical technique known as an inverse layout tree (ILT). The inverse layout tree is a forest of trees each rooted at a leaf node of the layout tree. Thus, in a typical implementation, a design mask shape would form the root of an inverse layout tree, while the leaves would represent flat layouts of the rooted mask shape. The use of the inverse layout tree has provided a means for manipulating instances of a mask shape at varying levels of nesting, from the most nested form to the most denested form. This enables the performance of design verification without any restriction on circuit overlap.
However, even with the advent of the inverse layout tree, several important problems remain unaddressed. One key problem involves efficient building of pruned inverse layout trees. The known techniques for building inverse layout trees use a Boolean variable at each node to indicate whether the node is to be included in the pruned tree. As a result, the full inverse layout tree must be built first in order to generate a pruned version. A second problem is pruning of inverse layout trees. The use of a Boolean variable at each node does not yield a maximally pruned inverse layout tree (ILT). As a result, the trees carry many unnecessary nodes. A third problem is reusabilty of pruned inverse layout trees. The Boolean variables at the ILT nodes do not retain the reason for the pruning. As a result, each ILT is specific to its particular check, and cannot be reused even in the event a subsequent check requires the exact same intrusion searches. A fourth problem is minimizing the number of checking computations. Existing algorithms do not provide a minimum computational model. Instead, nodes are simply re-checked multiple times and the required data is re-accumulated for each check, leading to a corresponding performance penalty. A fifth problem is expressing and handling new data applicable to only a portion of an existing circuit design. Using existing techniques, new data will typically cause flattening of the design, which in turn results in a significant performance penalty during verification.
The present invention addresses these and other heretofore unresolved limitations in the field of circuit design verification.